package seach

import (
	"fmt"
	"math"
)



//二分查找,sortedLi 已排序
func MidSearch(sortedLi []int, t int) int {
	fmt.Println("starting")
	left := 0
	right := len(sortedLi) - 1

	for right >= left {
		mid := int(math.Floor(float64((right + left) / 2)))
		if sortedLi[mid] == t {
			return mid
		}
		if sortedLi[mid] > t {
			right = mid - 1
			continue
		}
		if sortedLi[mid] < t {
			left = mid + 1
			continue
		}

	}
	return -1
}

//冒泡排序
func bubbleSort(li []int) []int {
	for i := 0; i < len(li)-1; i++ {
		c := false
		for j := 0; j < len(li)-1-i; j++ {
			if li[j] > li[j+1] {
				li[j], li[j+1] = li[j+1], li[j]
				c = true
			}
		}
		if !c {
			break
		}
	}
	return li
}

//快速排序-归位
func Partition(li []int, left, right int) (mid int) {
	tmpMid := (left + right) / 2
	li[left], li[tmpMid] = li[tmpMid], li[left]
	tmp := li[left]
	for left < right {
		for left < right && li[right] >= tmp { //找到比tmp小的数
			right = right - 1
		}
		li[left] = li[right]
		//fmt.Println("right",li)
		for left < right && li[left] <= tmp {
			left = left + 1
		}
		li[right] = li[left]
		//fmt.Println("left",li)
	}
	li[left] = tmp
	mid = left
	return mid
}

//快速排序
func QuickSort(li []int, left, right int) {
	if left < right {
		mid := Partition(li, left, right)
		QuickSort(li, left, mid-1)
		QuickSort(li, mid+1, right)
	}

}
